1. Field of the Invention
The present invention relates to a method and program for space-efficient representation of objects, and more particularly, a method and program for space-efficient representation of objects in a garbage-collected system.
2. Description of the Related Art
Embedded devices have long since become the most widely deployed computing platforms in the world, and the trend is continuing to accelerate. For such devices, including motes, smart cards, cellular phones, and handheld organizers, the flexibility to dynamically download new functionality is increasingly important. Often the downloaded software is not under the control of the maker of or service provider for the device.
Therefore, a premium is placed on reliability of the downloaded code—while consumers are regrettably accustomed to crashes on the part of personal computer operating systems, consumers are much less accepting when “necessary” devices like cellular phones cease to function. As a result, the Java computing platform is becoming steadily more attractive for embedded devices due to its safety properties, since arbitrary downloaded software can not compromise the operating system or other applications. A key contributor to these safety properties is garbage collection.
While some applications have real-time requirements, there are many which do not. Furthermore, the additional complexity, space, and time overheads necessarily associated with real-time collectors are in direct conflict with many of the other requirements imposed by memory-constrained embedded systems.
The requirements on garbage collectors in such embedded environments are:
Code Size: It is imperative that the virtual machine consume as little code space as possible. As a result, many typical methods for improving collector performance are inappropriate because of the resulting complexity and concomitant increase in code size;
Memory Overhead: The overhead due to collector meta-data and memory fragmentation should be kept to an absolute minimum. As a result, semi-space copying collectors are not an option;
Compaction: Since many embedded applications tun continuously for extended periods of time, the collector must be able to perform memory compaction, both to avoid arbitrary space consumption due to fragmentation, and to enable the virtual machine to release memory resources to the operating system as needed;
Reliability: System failure is not acceptable. This places a premium on both simplicity and on strong enforcement of invariants within the collector;
Smooth Performance: The likelihood that the application will run in a very constricted memory space is much higher than in PC- or server-based virtual machines. Therefore, the collector's performance should degrade gracefully as memory is reduced; and
Speed: Within the limits of the preceding requirements, the collector should be as fast as possible. Trading a small amount of space for a large improvement in time is acceptable for some, but not all, applications;
However, conventional systems and methods of garbage collection in such embedded environments experience several problems.
The tight memory requirements place a number of restrictions on the system which will be counter-intuitive to those working on desktop or server virtual machines. These issues arise both in the allocation strategy and in the garbage collection methodology.
First of all, inlining the allocation sequence is only done if the inlined code is (statically) shorter than the save/call/restore code sequence, since inlining would otherwise lead to significant code expansion.
Secondly, many popular free space organization schemes are unacceptable due to their high rate of fragmentation. Examples include binary buddy and systems that compose all objects out of a single small block size. The latter eliminate all external fragmentation at the expense of greatly increased internal fragmentation as well as increased access times, especially for array elements.
Other unfamiliar issues that arise in the embedded domain are the use of physical rather than virtually addressed memory, which makes a number of implementation techniques impossible; various types of segmented memory architectures, either due to the small architected word size of the processor, or to blocked allocation of non-virtual memory by the operating system; differing levels of memory performance (SRAM, DRAM, flash, etc.); and the requirement to reduce power consumption.
One author has evaluated the power consumption properties of different parts of memory in an embedded Java virtual machine (JVM), and discussed the collection strategies to minimize power consumption, particularly in a banked memory system where banks can be powered on and off individually. In subsequent work, the author used dynamic compression techniques to reduce the memory requirements of the application.
The author used two strategies: first, when heap space is exhausted, compression was performed on infrequently accessed objects. Second, allocating infrequently used fields of objects was avoided.
In the period from the early 1960's to the mid-1970's, Lisp systems ran with similar amounts of real memory as are available in today's smaller embedded environments, and there is therefore considerable related work from this time period.
However, significant amounts of this pioneering work was driven by the desire to reduce paging. The semi-space copying collectors were a response to this pressure.
Garbage collection in many early Lisp systems was considerably simplified by virtue of the fact that all memory consisted of CONS cells, which are of a uniform size. This assumption was also implicit in the design of Baker's Treadmill real-time collector.
Another author has advocated an approach to eliminating external fragmentation in systems with variable object sizes: there is a single block size (32 or 64 bytes) and all objects larger than that size are made up of multiple blocks which are not necessarily contiguous. Arrays are represented as trees.
There are two major problems with this approach: the first is that it simply trades external for internal fragmentation, which can easily reach 50%. Second, access to large objects becomes expensive—in particular, array element access, normally an indexed load instruction, becomes a tree walk operation. Performance overheads can therefore be very large.
A number of variations of region-based memory management have been tried. While automatically inferred regions can reduce the load on the garbage collector, they can not satisfactorily handle objects that have lifetimes that are not stack-like. Explicit regions significantly complicate the programming model, lead to brittle code, and expose more run-time errors. We have shown that garbage collection can run in constrained memory with good performance, obviating many of the reasons for using regions.
Still another author has claimed that fragmentation is not a “real world” problem and that it is feasible to build non-compacting collectors. However, the authors's measurements are for unrealistically short-lived programs.
Much of the work on real-time garbage collection overlaps in its concerns with pure embedded collection, although the real-time concerns often lead to reduced throughput and increased complexity.
For real-time or embedded systems, it is very important to be able to know the memory requirements of a given application. One approach is to analyze the live memory requirements using a combination of programmer annotation of pointer types and recursion depths, and automatic analysis.